package top.hkyzf.study.leetcode;

import org.junit.Test;

/**
 * @author 朱峰
 * @date 2022-2-3 18:08
 */
public class 和为K的最少斐波那契数字数目_1414 {
    public int findMinFibonacciNumbers(int k) {
        int result = 0;
        k = calc(k);
        while (k != -1) {
            k = calc(k);
            result++;
        }
        result++;
        return result;
    }

    int calc(int k) {
        if (k == 1) {
            return -1;
        }
        int fib = 0;
        int prev = 1;
        int next = 1;
        while (fib < k) {
            fib = prev + next;
            prev = next;
            next = fib;
        }
        if (fib == k) {
            return -1;
        }
        return k - prev;
    }

    @Test
    public void testFindMinFibonacciNumbers () {
        int k = 12;
        System.out.println(findMinFibonacciNumbers(k));
    }
}
